#include <iostream>
#include <vector>

using namespace std;

/*
核心思想：dp[i][j]表示的意思就是从i到j是不是回文串
子回文串的长度从2开始遍历，知道length

*/
class Solution {
public:
    string longestPalindrome(string s) {
        int max_length = 1;
        int begin = 0;
        int length = s.size();
        if (length < 2) return s;
        
        vector<vector<int>> dp(length, vector<int>(length, 0));

        // 初始化
        for (size_t i = 0; i < length; i++){
            dp[i][i] == 1;
        }

        // 开始遍历
        for (size_t L = 2; L < length + 1; L++){

            for (size_t i = 0; i < length; i++){
                int j = L + i - 1;
                if (j >= length) break;
                
                if (s[i] == s[j]) {
                    if (j - i < 3) dp[i][j] = 1;
                    else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if (dp[i][j]==1 && j - i + 1 > max_length) {
                    max_length = j - i + 1;
                    begin = i;
                }

            }
            
        }

        return s.substr(begin, max_length);
    }
};


int main(int argc, char *argv[]) {
    Solution solution;
    string s1 = "baab";
    string s2 = solution.longestPalindrome(s1);
    cout << "result : "<<endl<<s2<<endl;
    return 0;
}